/*
Frank
CAU
2019/11/23
*/
#ifndef FUCC
#define FUCC
#include "parse_tree_def.h"
#include <ctype.h>
#include <iostream>
#include <list>
#include <queue>
#include <stdio.h>
#include <string.h>
#define BUFFER_SIZE 20

using namespace std;

// global variables
// 用来存储当前的变量
char *token_buffer;
char *g_head;       //保存公式指针
char *g_peek;       //当前位置
bool g_neg;        //是否否定
char g_name;       //节点名称
node *g_hot;       //当前节点
vlist g_prid_vars; //谓词变量列表
char _var;        //单个变量
//以上变量将会在顺序读取时进行修改，全局共享

enum token
{              //供eat()使用
    LBRANK,    //左括号
    RBRANK,    //右括号
    PREDICATE, //谓词（变量会一起读取）
    QUANTITY,  //量词
    CONJKTION, //连接词
    NEGA,
    END,      //读取完成
    UNRECGNZ, //未知字符
    ERROR     //错误字符
};

void erase_space_tab(string &s)
{
    int index = 0;
    if (!s.empty())
    {
        while ((index = s.find(' ', index)) != string::npos)
        {
            s.erase(index, 1);
        }
        index = 0;
        while ((index = s.find('\t', index)) != string::npos)
        {
            s.erase(index, 1);
        }
    }
}
token eat()
{ //将g_peek指针向前推移
    // 同时修改token_buffer
    char c = *g_peek;
    if (c == '\0')
    {
        g_peek++;
        return END;
    }
    if (c == '~')
    {
        g_peek++;
        return NEGA;
    }
    if (c == ')')
    {
        g_peek++;
        return RBRANK; //右括号
    }
    if (c == '(')
    {
        if (*(g_peek + 1) == '@' | *(g_peek + 1) == '#')
        {
            // 量词
            // ->(@x)
            // 指针向前移动
            g_neg = false;
            g_name = *(g_peek + 1); //获取字母
            _var = *(g_peek + 2);
            g_peek += 4;
            return QUANTITY;
        }
        else
        {
            // TODO
            // 有没有错误检测
            g_peek++;
            return LBRANK; //左括号
        }
    }
    if (c == '!' || c == '%' || c == '>')
    {           //连接词
        g_peek++; //跳过连接符
        g_name = c;
        return CONJKTION;
    }
    if (c > 'A' && c < 'Z')
    { //谓词
        // P(x,y,z)!()
        // P(x)!
        // 注册字母
        g_name = c;
        g_neg = false;
        // 跳到第一个变量
        g_peek += 2;
        string vs;
        if (*(g_peek - 1) == '(' && islower(*(g_peek)))
        {                    //左括号和字母
            vs = vs + *g_peek; //添加第一个字符
        }
        else
        {
            error(ERR_BADFMT, g_hot);
            return ERROR;
        }
        while (*(g_peek + 1) == ',')
        {              //是一个逗号
            g_peek += 2; //跳过逗号
            if (islower(*g_peek))
            { //是一个小写字母
                vs = vs + *g_peek;
            }
            else
            {
                // 格式错误
                error(ERR_BADFMT, g_hot);
                return ERROR;
            }
            // 现在g_peek的位置是一个小写字母
        }
        // 退出,g_peek相当于在z的位置
        if (*(g_peek + 1) == ')')
        {
            g_peek += 2;
        }
        // g_peek已经移出括号
        char *ss = (char *)vs.data();
        g_prid_vars = new_vars(ss);

        return PREDICATE;
    }
    error(ERR_UNRECG, g_hot);
    return UNRECGNZ;
}

char *flush_buffer()
{
    //清空缓冲区
    delete[] token_buffer;
    token_buffer = new char[BUFFER_SIZE];
    return token_buffer;
}

node *splay(node *current, char *ss)
{ //从当前节点开始生长

    if (current == NULL)
    { //空节点
        error(ERR_NULLNODE, g_hot);
    }
    g_peek = ss;
    g_head = g_peek;
    g_hot = current;
    while (true)
    { //不断循环
        switch (token t = eat())
        {                              //根据缓冲区内的内容，如果是
        case LBRANK:                   //左括号
            g_hot = g_hot->descend_lc(); //产生左子节点
            break;
        case CONJKTION: //连接词
            if (!g_hot->to_conj(g_name))
            { //如果为真则已经完成转换
                //返回空值代表该节点已经被定义
                // 格式错误
                printf("连接词%c可能错误", g_name);
                error(ERR_BADFMT, g_hot);
            }
            g_hot = g_hot->descend_rc(); //创建右节点
            break;
        case PREDICATE: //谓词
            if (!g_hot->to_prid(g_neg, g_name, g_prid_vars))
            {
                //返回空值代表该节点已经被定义
                printf("谓词%c到达已定义节点", g_name);
                error(ERR_BADFMT, g_hot);
            }
            g_hot = g_hot->ascend(); //上溯
            break;
        case QUANTITY: //量词
            g_hot->to_quant(g_name, _var);
            g_hot = g_hot->descend_lc(); //创建空子节点
            break;
        case NEGA: //原生否定符号
            g_hot->to_rawneg();
            g_hot = g_hot->descend_lc();
            break;
        case RBRANK:               //右括号
            g_hot = g_hot->ascend(); //上溯至父节点
            break;
        case END: //直至停止
        default:
            return g_hot;
        }
    }
}

void hierarchical_traverse(node *root, void (*visit)(node *))
{ //层序遍历
    printf("\t**********层序遍历********* 根节点:");
    show(root);
    printf("\n");

    queue<node *> q, layer;
    node *cur;
    layer.push(root);
    int count = 1;
    while (!layer.empty())
    {
        while (!layer.empty())
        {
            q.push(layer.front());
            layer.pop();
        }

        while (!q.empty())
        {
            cur = q.front();
            q.pop();
            if (cur->_lc) //左孩子非空
                layer.push(cur->_lc);
            if (cur->_rc)
                layer.push(cur->_rc);
            visit(cur);

        }
        printf("\n");
        count++;
    }
}

/*
注意，下面的方法也是层序遍历，不同的是
这种方法采用了两个队列，可以在某个循环体当中访问同层的所有元素
具体地，可以实现诸如对层计数的操作
*/

// void hierarchical_traverse(node *root, void (*visit)(node *))
// { //层序遍历
//     printf("\t**********层序遍历********* 根节点:");
//     show(root);
//     printf("\n");

//     queue<node *> q;
//     q.push(root);
//     node *cur;
//     int count = 1;

//     while (!q.empty())
//     {
//         cur = q.front();
//         q.pop();
//         if (cur->_lc) //左孩子非空
//             q.push(cur->_lc);
//         if (cur->_rc)
//             q.push(cur->_rc);
//             // 一定注意!!不要先访问再append
//             // 因为这个过程中可能会删除节点
//             // 这时实际上 cur->_lc 并不是空
//             // 但已经初始化为一个诸如0xfffefffe的非空值了,会使之后的操作崩溃
//             // 可以尝试更改顺序,会出现段错误
//         visit(cur);
//         printf("\n");
//         count++;
//     }

// }


// 重载
// 为了可以传入不同的函数指针类型
// 因为实际上也是连入了其他的函数

void hierarchical_traverse(node *root, void (*visit)(node *, char oldc, char newc), char old_c, char new_c)
{ //层序遍历
    printf("\t**********层序遍历********* 根节点:");
    show(root);
    printf("\n");

    queue<node *> q;
    queue<node *> layer;
    node *cur;
    layer.push(root);
    int count = 1;
    while (!layer.empty())
    {
        while (!layer.empty())
        {
            q.push(layer.front());
            layer.pop();
        }

        while (!q.empty())
        {
            cur = q.front();
            visit(cur, old_c, new_c);
            q.pop();
            if (cur->_lc) //左孩子非空
                layer.push(cur->_lc);
            if (cur->_rc)
                layer.push(cur->_rc);
        }
        printf("\n");
        count++;
    }
}

// void hierarchical_traverse(node *root, void (*visit)(node *, char oldc, char newc), char old_c, char new_c)
// { //层序遍历
//     printf("\t**********层序遍历********* 根节点:");
//     show(root);
//     printf("\n");

//     queue<node *> q;
//     q.push(root);
//     node *cur;
//     int count = 1;

//     while (!q.empty())
//     {
//         cur = q.front();
//         q.pop();
//         if (cur->_lc) //左孩子非空
//             q.push(cur->_lc);
//         if (cur->_rc)
//             q.push(cur->_rc);
//         // 一定注意!!不要先访问再append
//         // 因为这个过程中可能会删除节点
//         // 这时实际上 cur->_lc 并不是空
//         // 但已经初始化为一个诸如0xfffefffe的非空值了,会使之后的操作崩溃
//         // 可以尝试更改顺序,会出现段错误
//         visit(cur,old_c,new_c);
//         printf("\n");
//         count++;
//     }
// }


struct same_alpha
{ //一个变量指针的集合
    // 意味着这些变量统一都需要更改为 new_var;
    list<variable *> *v_ptrs;
    char new_var;
    same_alpha() : v_ptrs(null), new_var('^') { this->v_ptrs = new list<variable *>(); };
    same_alpha(char new_alpha) : new_var(new_alpha) { this->v_ptrs = new list<variable *>(); };
    void append(variable *v);
};

void same_alpha::append(variable *v)
{ //添加一个variable节点
    printf("调用append: 待替换变量%c\n", v->_v);
    this->v_ptrs->push_back(v);
}



// 一个特殊的全局变量,如果为真,则在其值为真期间,所有的存在量词辖域内,例如(#y),相应的变量都需要替换为 $,代表 f(x)
// 否则,应该替换为1(代替常量)
bool under_all = false;

void check_prid(node *n, char old_var)
{
    if (n->_type == N_PRID && n->_vars != null)
    {
        printf("发现谓词", old_var);
        show(n);
        // 替换符号
        if (under_all == false)
        {
            printf("不在全称量词之下");
            // 函数
            change_alpha(n->_vars, old_var, '1');
        }
        else
        {
            // 常量
            printf("在全称量词之下");
            change_alpha(n->_vars, old_var, '$');
        }
        printf(" 替换之后");
        show(n);
        printf("\n");
    }
    else
    {
        return;
    }
}

void DLR_register_all(node *root, void (*alter_prid)(node *, char), char old_alpha)
{ //不只是先序遍历，同时注册全称量词
    // 若想进行注册，也可以设置全局变量var_all_above保存
    // 在退出时删除节点
    if (root == null)
    {
        return;
    }
    else
    {
        if (root->_sym == '@' && root->_type == N_QUANT)
        { //全称量词
            // 之后的操作都要进行
            printf("发现全称量词");
            show(root);
            printf("修改under_all变量为true");

            under_all = true;
            printf("\n");
            // 根节点不进行操作
            // 之后所有的节点都替换's'
            DLR_register_all(root->_lc, alter_prid, old_alpha);
            DLR_register_all(root->_rc, alter_prid, old_alpha);
            // 重要
            printf("修改under_all变量为flase");
            under_all = false;
        }
        else if (root->_type == N_QUANT && root->_sym == '#')
        { //是存在量词
            printf("\t发现存在量词");
            show(root);
            printf("\n");
            // 根节点不做操作
            // 记录节点
            char old_var = get_var(root->_vars);
            // alter_prid(root, old_alpha);
            // 此后的所有遍历操作，都将根据old_var进行
            DLR_register_all(root->_lc, alter_prid, old_var);
            delete_merge(root);
            // 删除该节点
        }
        else
        { //其他
            // 继续使用默认的old_alpha 进行遍历
            alter_prid(root, old_alpha);
            DLR_register_all(root->_lc, alter_prid, old_alpha);
            DLR_register_all(root->_rc, alter_prid, old_alpha);
        }
    }
}

void init_func()
{ //重置变量
    //TODO
}

void erase_exsits(node *root)
{
    // 消除所有的存在量词
    // 采用基于标志位的二叉树先序遍历
    DLR_register_all(root, check_prid, '\0');
}
#endif